package _17_graph;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author: mornd
 * @dateTime: 2023/6/26 - 11:36
 * 最小生成树-Kruskal (克鲁斯卡尔) 算法
 */
public class Kruskal {
    static class Edge implements Comparable<Edge> {
        List<Vertex> vertices;
        // 数组索引
        int start;
        int end;
        int weight;

        public Edge(List<Vertex> vertices, int start, int end, int weight) {
            this.vertices = vertices;
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(weight, o.weight);
        }

        @Override
        public String toString() {
            return vertices.get(start).name + "-" + vertices.get(end).name + " (" + weight + ")";
        }
    }

    @Test
    public void test() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");

        List<Vertex> vertices = List.of(v1, v2, v3, v4, v5, v6, v7);

        // 参照 img/最小生成树.png
        PriorityQueue<Edge> queue = new PriorityQueue<>(List.of(
                // 该边连接的是下标0(v1)和1(v2)的顶点，并且权重为2
                new Edge(vertices, 0, 1, 2),
                new Edge(vertices, 0, 2, 4),
                new Edge(vertices, 0, 3, 1),
                new Edge(vertices, 1, 3, 3),
                new Edge(vertices, 1, 4, 10),
                new Edge(vertices, 2, 3, 2),
                new Edge(vertices, 1, 5, 5),
                new Edge(vertices, 3, 4, 7),
                new Edge(vertices, 3, 5, 8),
                new Edge(vertices, 3, 6, 4),
                new Edge(vertices, 4, 6, 6),
                new Edge(vertices, 5, 6, 1)
        ));

        kruskal(vertices.size(), queue);
    }

    private void kruskal(int size, PriorityQueue<Edge> queue) {
        List<Edge> list = new ArrayList<>();
        DisJoinSet set = new DisJoinSet(size);

        while (list.size() < size - 1) {
            Edge poll = queue.poll();
            int i = set.find(poll.start);
            int j = set.find(poll.end);
            if(i != j) {
                // 不相交
                set.union(i, j); // 使其相交
                list.add(poll);
            }
        }

        for (Edge edge : list) {
            System.out.println(edge);
        }
    }
}
